/**
 * SudoService.java
 */
package tk.sunlatus.game.sudo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author Sunlotus
 * 
 */
public class SudoService {

    private Set<Integer> checker = new HashSet<Integer>();

    private boolean needInit = false;

    /**
     * 回溯标志
     */
    private boolean fillBackFlag = false;

    /**
     * 单步模式
     */
    private boolean stepByStepFlag = false;

    SudoStack stack = new SudoStack();

    public SudoStruct generateSudo() {
        return generateSudo(0);
    }

    public SudoStruct generateSudo(int level) {

        // 生成棋盘
        int[][] src = generateSoduArray();
        // 挖洞
        hideValue(src, level);
        SudoStruct sudo = new SudoStruct();
        sudo.setSudo(src);
        return sudo;
    }

    /**
     * 方法描述：求解
     * 
     * @param sudo
     * @return
     */
    public SudoStruct decode(SudoStruct sudo) {
        boolean fillFlag = true;
        // System.out.println("*************************************");
        endDecode: for (int x = 1; x < sudo.getSudo().length + 1; x++) {
            for (int y = 1; y < sudo.getSudo()[x - 1].length + 1; y++) {
                if (sudo.isNotEmpty(x, y)) {
                    continue;
                }

                needInit = true;
                checkX(sudo, x, y, true);
                needInit = false;
                checkY(sudo, x, y, true);
                checkXY(sudo, x, y, true);
                // System.out.println("[" + x + "," + y + "]=" +
                // Arrays.toString(checker.toArray()));
                if (checker.size() == 1) {
                    sudo.fill(x, y, checker.toArray(new Integer[1])[0]);
                    if (fillBackFlag) {
                        stack.push(new Location(x, y, new HashSet<Integer>()));
                    }
                    // 解码完毕，退出循环
                    if (!sudo.isNotAllFill()) {
                        fillFlag = false;
                        break endDecode;
                    }
                    if (stepByStepFlag) {
                        return sudo;
                    }

                }
                // 无可用值，说明前面填充有无
                else if (checker.size() == 0) {
                    return fillBack(sudo, stack.pop());
                }
            }
        }
        if (fillFlag) {
            if (sudo.isNotAllFill()) {
                fillBackFlag = true;
                Location location = getLocation(sudo);
                stack.push(location);
                // 回溯填充
                return fillBack(sudo, location);
            }
            stack.clear();
            return sudo;
        }
        return decode(sudo);
    }

    /**
     * 方法描述： 回溯填充
     * 
     * @param sudo
     * @param location
     * @return
     */
    private SudoStruct fillBack(SudoStruct sudo, Location location) {
        sudo.fill(location.getX(), location.getY(), 0);
        // TODO 回溯
        int value = location.nextValue();
        if (value == 0) {
            location = stack.pop();
            // 解码失败
            if (location == null) {
                return sudo;
            }
            return fillBack(sudo, location);
        }
        if (location.getValues().size() > 0) {
            stack.push(location);
        }
        sudo.fill(location.getX(), location.getY(), value);
        if (stepByStepFlag) {
            return sudo;
        }
        return decode(sudo);
    }

    /**
     * 方法描述：获取空白位置，及可用值
     * 
     * @param sudo
     * @return
     */
    private Location getLocation(SudoStruct sudo) {
        Location l = new Location();
        for (int i = 0; i < sudo.getSudoStatus().length; i++) {
            for (int j = 0; j < sudo.getSudoStatus()[i].length; j++) {
                if (sudo.getSudoStatus()[i][j] == SudoStruct.STATUS_EMPTY) {
                    needInit = true;
                    checkX(sudo, i + 1, j + 1, true);
                    needInit = false;
                    checkY(sudo, i + 1, j + 1, true);
                    checkXY(sudo, i + 1, j + 1, true);
                    l.setX(i + 1);
                    l.setY(j + 1);
                    l.setValues(new ArrayList<Integer>(checker));
                    return l;
                }
            }
        }

        return l;
    }

    private void checkY(SudoStruct sudo, int x, int y, boolean checkSpecifiedLocation) {
        Set<Integer> nums = initChecker();
        // if (sudo.isNotEmpty(x, y)) {
        // nums.remove(sudo.get(x, y));
        // }

        for (int i = 0; i < sudo.getSudo().length; i++) {
            if (!checkSpecifiedLocation && i == x - 1) {
                continue;
            }
            if (nums.contains(sudo.getSudo()[i][y - 1])) {
                nums.remove(sudo.getSudo()[i][y - 1]);
            }
        }

    }

    public static void main(String[] args) {

        String src = "400706005736915082915082000804307109067109820009820367008603501070091000091200600";
        // src =
        // "060000004000000000000000000200070908100900700009060000000600809040020105000000000";
        src = "000000000000000000000000000000000000000000000000000000000000000000000000000000000";
        SudoStruct sudo = new SudoStruct();
        int[][] start = new int[9][9];
        start = getStart(src);
        sudo.setSudo(start);
        sudo.show(sudo.getSudo());
        sudo.show(sudo.getSudoStatus());
        SudoService sudoService = new SudoService();
        // sudoService.setStepByStepFlag(true);
        long startTime = System.currentTimeMillis();
        sudoService.decode(sudo);
        long end = System.currentTimeMillis();
        System.out.println(end - startTime + " ms");
        sudo.show(sudo.getSudo());
        sudo.show(sudo.getSudoStatus());
        System.out.println(sudoService.isValidate(sudo));
    }

    private void checkX(SudoStruct sudo, int x, int y, boolean checkSpecifiedLocation) {
        Set<Integer> nums = initChecker();
        for (int i = 0; i < sudo.getSudo()[x - 1].length; i++) {
            if (!checkSpecifiedLocation && i == y - 1) {
                continue;
            }
            if (nums.contains(sudo.getSudo()[x - 1][i])) {
                nums.remove(sudo.getSudo()[x - 1][i]);
            }
        }
    }

    private static int[][] getStart(String str) {
        // str =
        // "020900010006000205050000060804000000600700000100080004581007942269000357743295186";
        // str =
        // "397000000600700010800305000032050600000804000008060250000602001070009008000000769";
        int[][] array = new int[9][9];
        int x = 0;
        int y = 0;
        for (int i = 0; i < str.length(); i++) {
            if (x > 9 && i % 9 == 0) {
                x = i - 1 / 9;
                y = 8;
            } else {
                x = i / 9;
                y = i % 9;
            }
            array[x][y] = Integer.valueOf(str.substring(i, i + 1));
        }
        return array;
    }

    private void checkXY(SudoStruct sudo, int x, int y, boolean checkSpecifiedLocation) {
        Set<Integer> nums = initChecker();
        int sudox = sudo.getLocationX(x);
        int sudoy = sudo.getLocationY(y);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (!checkSpecifiedLocation && sudox * 3 + i + 1 == x && sudoy * 3 + j + 1 == y) {
                    continue;
                }
                nums.remove(sudo.get(sudox * 3 + i + 1, sudoy * 3 + j + 1));
            }
        }

    }

    private Set<Integer> initChecker() {
        if (needInit) {
            checker.clear();
            for (int i = 0; i < 9; i++) {
                checker.add(i + 1);
            }
        }
        return checker;
    }

    /**
     * 方法描述：生成完整数独矩阵
     * 
     * @return
     */
    private int[][] generateSoduArray() {
        int[][] center = generateCenter();
        int[][] leftCenter = centerShift2Down(center, 1);
        int[][] rightCenter = centerShift2Down(center, 2);
        int[][] upCenter = centerShift2Right(center, 1);
        int[][] downCenter = centerShift2Right(center, 2);
        int[][] leftup = centerShift2Right(leftCenter, 1);
        int[][] leftDown = centerShift2Right(leftCenter, 2);
        int[][] rightUp = centerShift2Right(rightCenter, 1);
        int[][] rightDown = centerShift2Right(rightCenter, 2);

        int[][] result = new int[9][9];

        // 上三行
        for (int i = 0; i < leftup.length; i++) {
            System.arraycopy(leftup[i], 0, result[i], 0, leftup[i].length);
        }
        for (int i = 0; i < upCenter.length; i++) {
            System.arraycopy(upCenter[i], 0, result[i], 0 + leftup[i].length, upCenter[i].length);
        }
        for (int i = 0; i < rightUp.length; i++) {
            System.arraycopy(rightUp[i], 0, result[i], 0 + leftup[i].length + upCenter[i].length, rightUp[i].length);
        }

        // 中间三行
        for (int i = 0; i < leftCenter.length; i++) {
            System.arraycopy(leftCenter[i], 0, result[i + leftup.length], 0, leftCenter[i].length);
        }
        for (int i = 0; i < center.length; i++) {
            System.arraycopy(center[i], 0, result[i + upCenter.length], 0 + leftCenter[i].length, center[i].length);
        }
        for (int i = 0; i < rightCenter.length; i++) {

            System.arraycopy(rightCenter[i], 0, result[i + rightUp.length],
                0 + leftCenter[i].length + center[i].length, rightCenter[i].length);
        }

        // 下三行
        for (int i = 0; i < leftDown.length; i++) {
            System.arraycopy(leftDown[i], 0, result[i + leftup.length + leftCenter.length], 0, leftDown[i].length);
        }
        for (int i = 0; i < downCenter.length; i++) {
            System.arraycopy(downCenter[i], 0, result[i + upCenter.length + center.length], 0 + leftDown[i].length,
                downCenter[i].length);
        }
        for (int i = 0; i < rightDown.length; i++) {
            System.arraycopy(rightDown[i], 0, result[i + rightUp.length + rightCenter.length], 0 + leftDown[i].length
                + downCenter[i].length, rightDown[i].length);
        }

        return result;
    }

    /**
     * 方法描述：生成中心矩阵
     * 
     * @return
     */
    private int[][] generateCenter() {
        int[][] center = new int[3][3];
        List<Integer> values = getValues();
        // 打乱顺序
        Collections.shuffle(values);
        for (int i = 0; i < center.length; i++) {
            for (int j = 0; j < center[i].length; j++) {
                center[i][j] = values.remove(0);
            }
        }
        return center;
    }

    /**
     * 方法描述：矩阵列循环右移step位
     * 
     * @param center
     *            矩阵
     * @param step
     *            移位步长
     * @return
     */
    private int[][] centerShift2Down(int[][] center, int step) {
        int[][] upCenter = new int[3][3];
        for (int i = 0; i < center.length; i++) {
            for (int j = 0; j < center[i].length; j++) {
                upCenter[(i + step) % 3][j] = center[i][j];
            }
        }
        return upCenter;
    }

    /**
     * 方法描述：矩阵行循环下移step位
     * 
     * @param center
     *            矩阵
     * @return
     */
    private int[][] centerShift2Right(int[][] center, int step) {
        int[][] leftCenter = new int[3][3];
        for (int i = 0; i < center.length; i++) {
            for (int j = 0; j < center[i].length; j++) {
                // 列循环右移
                leftCenter[i][(j + step) % 3] = center[i][j];
            }
        }
        return leftCenter;
    }

    /**
     * 方法描述：获取1~9
     * 
     * @return
     */
    private List<Integer> getValues() {

        List<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < 9; i++)
            result.add(i + 1);

        return result;
    }

    /**
     * 方法描述：根据参数对数独矩阵进行部分数字擦除
     * 
     * @param level
     */
    private void hideValue(int[][] sudoArray, int level) {

        /**
         * 获取空格数
         */
        int blankCount = getBLankCount(level);
        // 获得空白位置
        Set<Integer> emptyValueLocations = getLocations(blankCount);

        int x = 0;
        int y = 0;
        for (Integer location : emptyValueLocations) {
            y = location % 9;
            x = (location - y) / 9;
            // System.out.println(location + ":" + x + "," + y);
            sudoArray[x][y] = 0;
        }

    }

    private Set<Integer> getLocations(int blankCount) {
        if (blankCount > 81) {
            blankCount = getBLankCount(10);
        }
        Set<Integer> result = new HashSet<Integer>(blankCount);
        while (result.size() < blankCount) {
            result.add((int) (Math.random() * 81));
        }
        return result;
    }

    private int getBLankCount(int level) {
         return 33 + (int) (level * 1.5);
//        return (int) (level * 1.5);
    }

    /**
     * @return the stepByStepFlag
     */
    public boolean isStepByStepFlag() {
        return stepByStepFlag;
    }

    /**
     * @param stepByStepFlag
     *            the stepByStepFlag to set
     */
    public void setStepByStepFlag(boolean stepByStepFlag) {
        this.stepByStepFlag = stepByStepFlag;
    }

    public boolean isValidate(SudoStruct sudo) {
        if (sudo.isNotAllFill()) {
            // System.out.println("sudo is not all fill.");
            return false;
        }
        for (int i = 0; i < sudo.getSudo().length; i++) {
            for (int j = 0; j < sudo.getSudo()[i].length; j++) {
                needInit = true;
                checkX(sudo, i + 1, j + 1, false);
                needInit = false;
                checkY(sudo, i + 1, j + 1, false);
                checkXY(sudo, i + 1, j + 1, false);
                if (checker.isEmpty() || checker.size() != 1) {
                    // System.out.println("location[" + (i + 1) + "," + (j + 1)
                    // + "]=" + checker.toString());
                    return false;
                }
            }
        }
        return true;

    }

}
